In an international standard of a moving image coding system such as MPEG-2, MPEG-4 or H.264, a motion vector indicating that a block to be coded resembles which position of a reference image is used. When the motion vector is proper, an error between the block and the reference image becomes small, and efficient coding becomes possible. On the other hand, when the motion vector is improper, an error becomes large, and coding efficiency is lowered. As stated above, the accuracy of the motion vector has a large influence on the coding efficiency.
Since motion vector search generally requires a large amount of operation, efficient motion vector search methods have been proposed. As examples of the high speed movement search methods, a hierarchical search method (see, for example, JP-A-2004-129099) and a search by a gradient method (see, for example, Shan Zhu and Kai-Kuang Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 9, NO. 2, FEBRUARY 2000) are named.
However, in the hierarchical search method, there is a problem that when a search range is widened, the number of search points is increased in proportion thereto.
On the other hand, in the gradient method, search points are compared, and a search is made while a shift is performed in the direction in which an evaluation value is good, and therefore, the number of search points may be small. However, in the gradient method, there is a problem that in the case where motion from the reference image is hard, an accurate motion vector can not be obtained.
Then, the present invention has been made in view of the above, and has an object to provide a motion vector search method, device and program, in which when a search is made for a motion vector, the accurate motion vector can be obtained, while an increase in processing amount and the like is suppressed.